\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{url}

%% Define a new 'leo' style for the package that will use a smaller font.
\makeatletter
\def\url@leostyle{%
  \@ifundefined{selectfont}{\def\UrlFont{\sf}}{\def\UrlFont{\small\ttfamily}}}
\makeatother
%% Now actually use the newly defined style.
\urlstyle{leo}

\title{Regular Expression Interpreter}
\author{Juho Häme}
\begin{document}

\maketitle

\section{Introduction}
The \emph{Regular Expression Interpreter} will be done as a part of the course Data Structures Project at University of Helsinki, Faculty of Computer Science, in May-June 2010. The course is a standard 4 credit course ECTS\cite{ects}.

\section{Goal}
The goal of is to create an algorithm to compile a given string into a finite automata relatively efficiently. Plain text may be fed to the automata, as strings or files, and it will accept or reject.

A substring matcher will also be supported, for finding matching expression(s) in a longer one.

\section{Efficiency}
The trivial solution to running input on a finite automata is to run one way, then run another, and another until an accepting state is reached or there are no more paths. This results in an worst case time complexity of $O(2^n)$, where $n$ is the amount of states in the automata. However, even in the worst case, space complexity is only $O(1)$.\cite{regex}

The algorithm used in \emph{Regular Expression Interpreter} is based on Ken Thompsons idea of trying all possible paths at once. This means keeping track of all non-rejecting states. Worst case space complexity is $O(n)$, but worst case time complexity is drastically better than in the trivial approach: $O(n^2)$.\cite{regex}

\begin{quote}
"Even a slow implementation of a linear-time algorithm can easily outperform a fast implementation of an exponential-time algorithm once the exponent is large enough."\cite{regex}
\end{quote}

\section{Implementation}
\emph{Regular Expression Interpreter} will be coded in Python 2.6 and will feature a simple textual user interface. Syntax for feeding regular expressions will follow a subset of standard regular expression syntax\cite{regex-syntax}.

\bibliographystyle{acm}
\bibliography{regexreader}

\end{document}